package com.kaifa.test;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Random;

/**
 * 二分法和冒泡排序
 */
public class DichotomySortDemo {
	
	public static void main(String[] args) {

		Random rm = new Random();
		int[] arr = new int[100000];
		for (int i = 0 ; i < arr.length ; i++) {
			arr[i] = rm.nextInt(1000000000);
		}
		int[] arr1 = arr.clone(); // 复制一份副本
		
		long start = System.currentTimeMillis();
		int[] sortedArr = dichotomySort(arr);
		long end = System.currentTimeMillis();
		System.out.println("二分法排序耗时：" + (end -start) + "; 排序后的数组是：");

		
		long start1 = System.currentTimeMillis();
		int[] sortedArr1 = bubbleSort(arr1);
		long end1 = System.currentTimeMillis();
		System.out.println("冒泡排序耗时：" + (end1 -start1) + "; 排序后的数组是：");
		Arrays.toString(sortedArr1); // 格式化打印
	}
	
	// 二分法排序
	public static int[] dichotomySort(int[] arr) {
		int[] temp = new int[arr.length]; // 创建一个临时数组用于存放数组
		for (int i = 0; i < temp.length; i++) { // 对元素进行遍历
			if (i == 0) {
				temp[i] = arr[i]; // 将传入的数组的第一个值赋值给临时数组
			} else {
				for (int j = 0, k = i - 1; j < i && k >= 0;) {
					// 获取temp中间的元素跟传入数组的第i个元素比较
					if (temp[(j + k) / 2] >= arr[i]) { // 中间索引元素大于等于arr[i]
						if ((j + k) / 2 == 0) { // 如果下标是0，表示是第一个元素，在该元素前插入该值
							for (int n = i; n > 0; n--) {
								temp[n] = temp[n - 1];
							}
							temp[0] = arr[i];
							break;
						} else if (temp[(j + k) / 2 - 1] <= arr[i]) {
							// 获取中间索引的前一个所以比较，如果小于等于arr[i]
							// 将元素全部前移，将arr[i]插入中间索引位置
							for (int n = i; n > (j + k) / 2; n--) {
								temp[n] = temp[n - 1];
							}
							temp[(j + k) / 2] = arr[i];
							break;
						} else { // 否则，索引前移，继续匹配
							k = (k + j) / 2 - 1;
						}
					} else if (temp[(j + k) / 2] < arr[i]) {
						// 逻辑类上
						if ((j + k) / 2 == i - 1) {
							temp[i] = arr[i];
							break;
						} else {
							j = (k + j) / 2 + 1;
						}
					}
				}
			}
		}
		return temp;
	}
	
	// 冒泡排序法
	public static int[] bubbleSort(int[] arr) {
		int tempValue = 0 ;
		for (int j = arr.length - 1; j > 0  ; j--) {
			// 从左向右遍历，将未排序的数组中的最大数字运送到剩余数组的最右边
			for (int i = 0 ; i < j - 1 ; i++) {
				if (arr[i] > arr[i+1]) { // 如果左边的值比右边的值大，则交换两者的位置
					tempValue = arr[i];
					arr[i] = arr[i+1];
					arr[i+1] = tempValue;
				}
			}
		}
		return arr;
	}
			
			
	// 格式化打印数据
	public static void showInfo(int[] arr){
		StringBuilder sBuilder = new StringBuilder("【 ");
		int count = 1;
		for (int i = 0 ; i < arr.length ; i++) {
			count++; // 计数器自增
			sBuilder.append(arr[i] + ", ");
			if(count % 12 == 0) {
				sBuilder.append("\n");
			}
		}
		sBuilder = sBuilder.deleteCharAt(sBuilder.lastIndexOf(","));
		sBuilder.append("】");
		System.out.println(sBuilder);
	}
}
